package com.cat.twoPointerTechnique;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-the-integer-added-to-array-ii/
 * @create 2025/8/7 14:08
 * @since JDK17
 */

public class Solution19 {
    public int minimumAddedInteger(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        // 都排升序
        int ans = Integer.MAX_VALUE, n = nums1.length, m = nums2.length, i, j, cnt;
        int l = Math.min(nums1[0] - nums2[m - 1], nums2[0] - nums1[n - 1]);
        int r = Math.max(nums1[n - 1] - nums2[0], nums2[m - 1] - nums1[0]);

        while (l <= r) {
            // nums[j] - x
            cnt = 0;
            for (i = 0, j = 0; i < n && j < m; ) {
                if (nums2[j] + l < nums1[i]) {
                    j++;
                } else if (nums2[j] + l > nums1[i]) {
                    i++;
                } else {
                    cnt++;
                    i++;
                    j++;
                }
            }
            if (cnt == m) {
                return l;
            }
            l++;
        }
        return ans;
    }
}
